package algm_sorc;



public class Quick_Sorc {
	public static void quick_sor(int[] arry, int low, int high) {
		int first = low;
		int last = high;
		System.out.println("测试git");
		
		if(first<=last){
			int key = arry[first];
			while (first < last) {
				while ((arry[last] >= key) && first < last) {
					last--;
				}
				if (first < last) {
					arry[first++] = arry[last];
				}
				while ((arry[first] <= key) && first < last) {
					first++;
				}
				if (first < last) {
					arry[last--] = arry[first];
				}
			}
			arry[first] = key;
			
			quick_sor(arry, low, first - 1);
			quick_sor(arry, first + 1, high);
		}

	}

	public static void main(String[] args) {
		int[] buf = new int[] { 5, 1, 2, 1, 8, 4, 4, 10, 7, 3 };
		// int[] buf = new int[] {5,1,2,3,8};

		/*
		 * for(int i=0; i<10; i++){ buf[i] = new Random().nextInt(10) + 1;
		 * System.out.print(buf[i]); System.out.print(","); }
		 * System.out.println();
		 */
		quick_sor(buf, 0, buf.length - 1);
		// quickSort2(buf,0,9);

		printalm(buf);
	}

	private static void printalm(int[] buf) {
		for (int i = 0; i < buf.length; i++) {
			System.out.print(buf[i]);
			System.out.print(",");

		}
		System.out.println();
	}

	public static void quickSort2(int[] arr, int low, int high) {
		int first, last, key, t;
		if (low > high) {
			return;
		}
		first = low;
		last = high;
		// key就是基准位
		key = arr[first];

		while (first < last) {
			// 先看右边，依次往左递减
			while (key <= arr[last] && first < last) {
				last--;
			}
			// 再看左边，依次往右递增
			while (key >= arr[first] && first < last) {
				first++;
			}
			// 如果满足条件则交换
			if (first < last) {
				t = arr[last];
				arr[last] = arr[first];
				arr[first] = t;
			}

		}
		// 最后将基准为与i和j相等位置的数字交换
		arr[low] = arr[first];
		arr[first] = key;
		// 递归调用左半数组
		quickSort2(arr, low, last - 1);
		// 递归调用右半数组
		quickSort2(arr, last + 1, high);
	}

}
